package rm.mk;

import java.util.ArrayList;
import java.util.List;

import rm.mk.data.City;
import rm.mk.data.Route;

public class RouteFinder extends AbstractFinder {

	public RouteFinder(List<City> cities) {
		super(cities);
	}

	public String findShortestRoute(int from, int to) {
		Meta low = C(from, to);

		StringBuilder sb = new StringBuilder(from + " do " + to + ": { ");

		int totalCost = 0;

		while (low != null) {
			sb.append(low.at + " -> " + (low.m == null || low.m.validRoute ? to : low.m.at)
					+ " cost(" + low.cost + "), ");
			totalCost += low.cost;

			if(!low.m.validRoute)
				low = low.m;
			else low = null;
		}

		sb.append("}  = " + totalCost);

		return sb.toString();
	}

	private class Meta {

		private int cost, at;
		private Meta m;
		private boolean validRoute = false;

		public Meta(int cost, Meta meta, int at) {
			this.cost = cost;
			this.at = at;
			this.m = meta;
		}

		public Meta(boolean b) {
			this.validRoute = b;
		}

		public int getTotalCost() {
			if (m == null)
				return cost;

			return this.cost + m.getTotalCost();
		}

		public boolean isValidRoute() {
			if (m != null)
				return m.isValidRoute();

			return this.validRoute;
		}
	}

	private Meta C(int at, int dest) {
		if (at == dest)
			return new Meta(true);

		City att = this.selectCity(at);
		if (att == null)
			return new Meta(false);
		if (att.getRoutes().size() == 0)
			return new Meta(false);

		List<Meta> costs = new ArrayList<Meta>();

		for (Route r : att.getRoutes())
			costs.add(new Meta(r.getCost(), C(r.getDestination(), dest), at));

		return min(costs);
	}

	private Meta min(List<Meta> costs) {
		Meta lowestCost = null;

		for (Meta m : costs)
			if (m.isValidRoute())
				if (lowestCost == null || m.getTotalCost() < lowestCost.getTotalCost())
					lowestCost = m;

		return lowestCost;
	}
}
